{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct the Rectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: constructRectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 所以，现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>你设计的矩形页面必须等于给定的目标面积。</li>\n",
    "\t<li>宽度 <code>W</code>&nbsp;不应大于长度 <code>L</code> ，换言之，要求 <code>L &gt;= W </code>。</li>\n",
    "\t<li>长度 <code>L</code> 和宽度 <code>W</code>&nbsp;之间的差距应当尽可能小。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回一个&nbsp;<em>数组</em>&nbsp;<code>[L, W]</code>，其中 <em><code>L</code> 和 <code>W</code> 是你按照顺序设计的网页的长度和宽度</em>。<br />\n",
    "&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> 4\n",
    "<strong>输出:</strong> [2, 2]\n",
    "<strong>解释:</strong> 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。\n",
    "但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> area = 37\n",
    "<strong>输出:</strong> [37,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> area = 122122\n",
    "<strong>输出:</strong> [427,286]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= area &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-the-rectangle](https://leetcode.cn/problems/construct-the-rectangle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-the-rectangle](https://leetcode.cn/problems/construct-the-rectangle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '37', '122122']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        n = int(area**0.5)\n",
    "        for i in range(n, 0, -1):\n",
    "            if area % i == 0:\n",
    "                L = max(i, area//i)\n",
    "                return [L, area//L]\n",
    "        return \"SB\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        LW = []\n",
    "        for i in range(1, area+1):\n",
    "            if area % i == 0:\n",
    "                if i >= area//i:\n",
    "                    LW.append([i, area//i])\n",
    "        dif_min = float(\"inf\")\n",
    "        re = []\n",
    "        for el in LW:\n",
    "            dif = el[0] - el[1]\n",
    "            if dif < dif_min:\n",
    "                re = el\n",
    "                dif_min = dif\n",
    "        print(re)\n",
    "        return  re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w,w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def constructRectangle(self, area: int) -> List[int]:\r\n",
    "\r\n",
    "        l, w = area, 1        \r\n",
    "        while l>=w:\r\n",
    "            if area % l == 0 and l * w == area:\r\n",
    "                ans = [l, w]\r\n",
    "            w+=1\r\n",
    "            l = area //w\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(area**0.5)\n",
    "        while area%w != 0:\n",
    "            w -= 1\n",
    "        return [area//w, w]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w=int(area**(0.5))\n",
    "        while area%w:\n",
    "            w-=1\n",
    "        return [area//w,w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "            for x in range(int(area ** 0.5), 0, -1):\n",
    "                 if area % x == 0:\n",
    "                    return [area // x, x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        l,r=area,1\n",
    "        for i in range(2,int(area**0.5+1)):\n",
    "            if area%i==0:\n",
    "                r=i\n",
    "                l=area//i\n",
    "        return [l,r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        import math\n",
    "        for i in range(math.ceil(sqrt(area)),area+1):\n",
    "            if area//i == area/i:\n",
    "                return [i,area//i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        sqrt_area = int(math.sqrt(area))\n",
    "        for i in range(sqrt_area, 0, -1):\n",
    "            if area % i == 0:\n",
    "                return [area // i, i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        best = 1\n",
    "        for i in range(2, int(area**(1/2)+1)):\n",
    "            if area%i==0:\n",
    "                best = i\n",
    "        return int(area/best), best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        i=1\n",
    "        p=1\n",
    "        while i**2<=area:\n",
    "            if area%i==0:\n",
    "                p=i\n",
    "            i+=1\n",
    "        return [area//p,p]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        for i in range(int(sqrt(area)), 0, -1):\n",
    "            if not area % i:\n",
    "                return [area//i, i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = 1\n",
    "        ans = []\n",
    "        while w * w <= area:\n",
    "            if area % w == 0:\n",
    "                l = area // w\n",
    "                ans = [l, w]\n",
    "            w += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        width = 0\n",
    "        length = 0\n",
    "        distance = area\n",
    "        for i in range(1, (int)(sqrt(area)) + 1):\n",
    "            if area % i == 0 and abs(i - area // i) < distance:\n",
    "                width = i\n",
    "                heigth = area // i\n",
    "                distance = abs(width - heigth)\n",
    "        \n",
    "        return [heigth, width]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        re = [0,0]\n",
    "        dt = float(\"inf\")\n",
    "        i  = 1\n",
    "        if area == 1: return [1,1]\n",
    "        while i <= area//2:\n",
    "            if area % i == 0:\n",
    "                l = area // i\n",
    "                w = i\n",
    "                if l >= w and l - w < dt:\n",
    "                    dt = l - w\n",
    "                    re[0] = l\n",
    "                    re[1] = w\n",
    "            i += 1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        for w in range(int(sqrt(area)), 0, -1):\n",
    "            if area % w == 0:\n",
    "                return(area // w, w)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        start = int(math.sqrt(area))\n",
    "        for i in range(start):\n",
    "            if area % (start - i) == 0:\n",
    "                return [int(area/(start - i)), start - i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        left = int(math.sqrt(area))\n",
    "        while area % left != 0:\n",
    "                left-=1\n",
    "        right = area // left\n",
    "        return [right, left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w != 0:\n",
    "            w -= 1\n",
    "        return [area // w, w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        ls = []\n",
    "        leng = int(math.sqrt(area))\n",
    "        for i in range(1,leng + 1):\n",
    "            if area % i == 0 :\n",
    "                ls.append(i)\n",
    "                ls.append(area//i)\n",
    "        return ls[-1:-3:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        left = int(math.sqrt(area))\n",
    "        right = int(math.sqrt(area))\n",
    "        while area % left != 0:\n",
    "                left-=1\n",
    "        right = area // left\n",
    "        return [right, left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        A = [0,0]\n",
    "        l,r = 1,area\n",
    "        while l < r:\n",
    "            B = (l+r)//2\n",
    "            ref = B * B\n",
    "            if ref == area:\n",
    "                return [B,B]\n",
    "            elif ref > area:\n",
    "                r = B -1\n",
    "            else:\n",
    "                l = B + 1\n",
    "        while r > 0:\n",
    "            if area % r == 0:\n",
    "                A[0] = area // r\n",
    "                A[1] = r\n",
    "                break\n",
    "            r -= 1\n",
    "        A.sort()\n",
    "        return A[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w= int(sqrt(area))\n",
    "        while area % w !=0:\n",
    "            w-=1\n",
    "        return [int(area/w),w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self,area: int) -> List[int]:\n",
    "        L = int(math.sqrt(area))\n",
    "        W = int(math.sqrt(area))\n",
    "        while L * W != area:\n",
    "            if L * W < area:\n",
    "                L += 1\n",
    "            elif L * W > area:\n",
    "                W -= 1\n",
    "        return[L,W]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        ans = [0, 0]\n",
    "        for i in range(1, int(pow(area, 0.5)) + 1):\n",
    "            if area % i == 0 and i > ans[0]:\n",
    "                ans[0] = i\n",
    "        ans[1] = area // ans[0]\n",
    "        if ans[0] < ans[1]:\n",
    "            return ans[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        res = [0] * 2\n",
    "        for i in range(1,int(math.sqrt(area)) + 1):\n",
    "            if area % i == 0:\n",
    "                res[0] = area // i\n",
    "                res[1] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        L = area\n",
    "        W = 1\n",
    "        root = area ** 0.5\n",
    "        result = [L, W]\n",
    "        while L >= root:\n",
    "            if area % L == 0:\n",
    "                W = int(area / L)\n",
    "                result = [L, W]\n",
    "            L = L - 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        for i in range(int(sqrt(area)),0,-1):\n",
    "            if area % i == 0 :\n",
    "                return [area//i,i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        ans = [0, 0]\n",
    "        for i in range(1, int(pow(area, 0.5)) + 1):\n",
    "            if area % i == 0 and i > ans[0]:\n",
    "                ans[0] = i\n",
    "        ans[1] = area // ans[0]\n",
    "        if ans[0] < ans[1]:\n",
    "            return ans[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        ans=[0,0]\n",
    "        sqrta=int(sqrt(area))\n",
    "        for i in range(1, sqrta+1):\n",
    "            S=area/i\n",
    "            if S%1==0:\n",
    "                ans[0]=i\n",
    "                ans[1]=int(S)\n",
    "            else:\n",
    "                pass\n",
    "        if ans[0]<ans[1]:\n",
    "            ans=ans[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        a=1\n",
    "        b=1\n",
    "        for i in range(1,int(area**0.5)+1):\n",
    "            if area%i==0:\n",
    "                a=i\n",
    "        return [area//a,a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        flag = int(sqrt(area))\n",
    "        fast,slow = area,1\n",
    "        while flag >= 1:\n",
    "            if area % flag == 0:\n",
    "                return [max(flag,area//flag),min(flag,area//flag)]\n",
    "            flag = flag - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        for i in range(int(sqrt(area)),0,-1):\n",
    "            if area%i==0:\n",
    "                return(area//i,i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def constructRectangle(self, area):\n",
    "        \"\"\"\n",
    "        :type area: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        for i in range(int(sqrt(area)), 0, -1):\n",
    "            if area % i == 0:\n",
    "                return [area//i, i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        root=math.sqrt(area)\n",
    "        w=math.ceil(root)\n",
    "        l=area/w\n",
    "        if int(root)!=root:\n",
    "            while w<=area and l>=1:\n",
    "                l=area/w\n",
    "                if int(l)==l:\n",
    "                    break\n",
    "                else:\n",
    "                    w+=1\n",
    "        return [w,int(l)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        # 1. 找出所有因数的组合\n",
    "        # 2. 剔除不符合条件2， 3 的需求\n",
    "        combiantion = []\n",
    "        for l in range(1, area+1):\n",
    "            if not area % l:\n",
    "                w = area // l\n",
    "                if l >= w :\n",
    "                    combiantion.append([l, w])\n",
    "        \n",
    "        return min(combiantion, key=lambda x: abs(x[1] - x[0]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        # 1. 找出所有因数的组合\n",
    "        # 2. 剔除不符合条件2， 3 的需求\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        # 找最大因子\n",
    "        ans = [0, 0]\n",
    "        for i in range(1, int(pow(area, 0.5)) + 1):\n",
    "            if area % i == 0 and i > ans[1]:\n",
    "                ans[1] = i\n",
    "        ans[0] = area // ans[1]\n",
    "        return ans\n",
    "\n",
    "        # i = int(pow(area, 0.5))\n",
    "        # while area % i:\n",
    "        #     i -= 1\n",
    "        # return [area // i, i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        mid = int(area**0.5)\n",
    "        for i in range(mid, 0, -1):\n",
    "            if area % i == 0:\n",
    "                return [area // i, i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution(object):\n",
    "    def constructRectangle(self, area):\n",
    "        \"\"\"\n",
    "        :type area: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        w = int(math.sqrt(area))\n",
    "        while area % w != 0:\n",
    "            w -= 1\n",
    "        return [int(area / w), w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        max_w=int(sqrt(area))\n",
    "        w=max_w\n",
    "        while True:\n",
    "            if area%w==0:\n",
    "                return [area//w,w]\n",
    "            w-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, round(area**0.5) + 1):\n",
    "            if area % i == 0:\n",
    "                res.append([area // i, i])\n",
    "        return res[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        n = int(area**0.5)\n",
    "        for i in range(n, 0, -1):\n",
    "            if area % i == 0:\n",
    "                L = max(i, area//i)\n",
    "                return [L, area//L]\n",
    "        return \"SB\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        ### 找到差值最小的因子组合，因子必须整数，且只有两个\n",
    "        min_value=inf\n",
    "        for i in range(1,int(area**0.5)+1):\n",
    "            j=area//i\n",
    "            if area%i==0:\n",
    "                if abs(i-j)<min_value:\n",
    "                    min_value=abs(i-j)\n",
    "                    a,b=i,j\n",
    "        return [max(a,b),min(a,b)]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        # 找最大因子\n",
    "        # ans = [0, 0]\n",
    "        # for i in range(1, int(pow(area, 0.5)) + 1):\n",
    "        #     if area % i == 0 and i > ans[0]:\n",
    "        #         ans[0] = i\n",
    "        # ans[1] = area // ans[0]\n",
    "        # if ans[0] < ans[1]:\n",
    "        #     return ans[::-1]\n",
    "        # return ans\n",
    "\n",
    "        i = int(pow(area, 0.5))\n",
    "        while area % i:\n",
    "            i -= 1\n",
    "        return [area // i, i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        l=list()\n",
    "        for i in range(1,area+1):\n",
    "            if(area%i==0):\n",
    "                l.append(i)\n",
    "        return [l[len(l)//2],area//l[len(l)//2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        for i in range(int(area**0.5)+1,-1,-1):\n",
    "            if area % i == 0:\n",
    "                return [area//i,i] if  area//i >= i else [i,area//i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        res = [area, 1]\n",
    "        w = 2\n",
    "        while w <= int(area**0.5):\n",
    "            if area % w == 0:\n",
    "                res = [area//w, w]\n",
    "            w += 1\n",
    "        \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        w = int(sqrt(area))\n",
    "        while area % w:\n",
    "            w -= 1\n",
    "        return [area // w, w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        for i in range(isqrt(area), 0, -1):\n",
    "            if area % i == 0:\n",
    "                return [area // i, i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        #宽度从1开始\n",
    "        w = 1\n",
    "        #长度L\n",
    "        l = area // w\n",
    "        #遍历\n",
    "        result = []\n",
    "        #从中间值开始向1值靠近，这样第一个满足area % w == 0的值就是所求列表\n",
    "        w = int(math.sqrt(area))\n",
    "        while w >= 1:\n",
    "            if area % w == 0:\n",
    "                return [area // w, w]\n",
    "            w -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def constructRectangle(self, area):\n",
    "        \"\"\"\n",
    "        :type area: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        w = int(area**0.5)\n",
    "        while area % w != 0:\n",
    "            w -= 1\n",
    "        return [area//w, w]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        # 找最大因子\n",
    "        ans = [0, 0]\n",
    "        for i in range(1, int(pow(area, 0.5)) + 1):\n",
    "            if area % i == 0 and i > ans[0]:\n",
    "                ans[0] = i\n",
    "        ans[1] = area // ans[0]\n",
    "        # if ans[0] < ans[1]:\n",
    "        #     return ans[::-1]\n",
    "        return ans[::-1]\n",
    "\n",
    "        # i = int(pow(area, 0.5))\n",
    "        # while area % i:\n",
    "        #     i -= 1\n",
    "        # return [area // i, i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        li=[]\n",
    "        for i in range(1,int(area/2)+2):\n",
    "            d=int(area/i)\n",
    "            if area%i==0 and d>=i:\n",
    "                li.append((d,i))\n",
    "        return list(li[-1])     \n",
    "       \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        if ( area % 2 != 0 and area % 3 != 0 and area % 7 != 0 and area % 5 != 0) and area % 127 != 0 and area % 307 != 0 and area % 239!= 0:\n",
    "            return [area,1]\n",
    "\n",
    "        ans_list = [area,1]\n",
    "        tmp = 1\n",
    "        for i in range(2,int(area/2) + 1):\n",
    "            if area % i == 0:\n",
    "                tmp = int(area / i )\n",
    "                if abs( tmp - i) < abs(ans_list[0] - ans_list[1]):\n",
    "                    ans_list[0] = tmp\n",
    "                    ans_list[1] = i\n",
    "\n",
    "                    print(tmp,i)\n",
    "\n",
    "        return ans_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        # 找最大因子\n",
    "        # ans = [0, 0]\n",
    "        # for i in range(1, int(pow(area, 0.5)) + 1):\n",
    "        #     if area % i == 0 and i > ans[0]:\n",
    "        #         ans[0] = i\n",
    "        # ans[1] = area // ans[0]\n",
    "        # if ans[0] < ans[1]:\n",
    "        #     return ans[::-1]\n",
    "        # return ans\n",
    "\n",
    "        i = int(pow(area, 0.5))\n",
    "        while area % i:\n",
    "            i -= 1\n",
    "        return [area // i, i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        i=int(pow(area,0.5))\n",
    "        while area%i!=0:\n",
    "            i-=1\n",
    "        return [area//i,i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, area: int) -> List[int]:\n",
    "        n = int(area**(1/2))\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(n,area+1):\n",
    "            if area%i == 0:\n",
    "                if i>=(area//i):\n",
    "                    return [i,area//i]\n",
    "                else:\n",
    "                    return [area//i,i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructRectangle(self, ar: int) -> List[int]:\n",
    "        t=int(sqrt(ar))\n",
    "        dif=ar-1\n",
    "        l,r=1,ar\n",
    "        for i in range(1,t+1):\n",
    "            if ar%i==0:\n",
    "                if dif>abs(ar//i-i):\n",
    "                    dif =abs(ar//i-i)\n",
    "                    l=ar//i\n",
    "                    r=i\n",
    "        if l<r:\n",
    "            return [r,l]\n",
    "        else:\n",
    "            return [l,r]\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
